<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=`, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>数组转树结构</title>
    <style>
        .conatiner{
            width: 80%;
            margin: 0 auto;
        }
    </style>
</head>
<body>
<div class="conatiner">
    <h1>1.树的操作</h1>
    <div><img src="images/640.png"/></div>
    <h1>2.树的遍历</h1>
    <p>树结构的常用场景之一就是遍历，而遍历又分为广度优先遍历、深度优先遍历。其中深度优先遍历是可递归的，而广度优先遍历是非递归的，通常用循环来实现。深度优先遍历又分为先序遍历、后序遍历，二叉树还有中序遍历，实现方法可以是递归，也可以是循环。</p>
    <div><img src="images/640.webp"/></div>
    <p>
        广度优先和深度优先的概念很简单，区别如下：
        <ul>
          <li>深度优先，访问完一颗子树再去访问后面的子树，而访问子树的时候，先访问根再访问根的子树，称为先序遍历；先访问子树再访问根，称为后序遍历。</li>
          <li>广度优先，即访问树结构的第n+1层前必须先访问完第n层</li>
        </ul>
    </p>
</div>


<script type="text/javascript">
    const list = [
        {id: 1, parentId: 0, name: 'menu1'},
        {id: 11, parentId: 1, name: 'menu11'},
        {id: 21, parentId: 2, name: 'menu21'},
        {id: 12, parentId: 11, name: 'menu12'},
        {id: 2, parentId: 0, name: 'menu2'},
    ]

    /**
     * 数组转树结构
     * @param arr
     * @returns {[]}
     */
    function listToTree(arr) {
        if (!Array.isArray(arr)) {
            return
        }
        const array = []
        const obj = {}
        for (let i = 0; i < arr.length; i++) {
            obj[arr[i].id] = arr[i]
        }
        for (let i = 0; i < arr.length; i++) {
            const parent = obj[arr[i].parentId]
            if (parent) {
                (parent.children || (parent.children = [])).push(arr[i])
            } else {
                array.push(arr[i])
            }
        }
        return array;
    }
    console.log(listToTree(list))
</script>
</body>
</html>
